
#ifndef __OCTREE_H__
#define __OCTREE_H__

#include "BBox.h"

class Octree
{
public:

	// Constructor
	Octree(const Real3 &_point, const Real3 &_extent, uchar _level = 1);
	~Octree();

	// Adds a triangle to the tree
	void AddTri(const Real3 &a, const Real3 &b, const Real3 &c);

	// Adds a bounding box to the tree
	void AddBox(const BBox &b);

	// Adds an octree to the tree
	void AddOctree(const Octree &t);

	// Gets the bounding box points of all the octrr
	void GetBoxPoints(vector<Real3> &ptr, const Real3 &pos);

	// Octree collisions
	friend bool OctreeCollisions(const Octree *ocA, const Real3 &posA, const Octree *ocB, const Real3 &posB);
	friend bool OctreeCollisions(const Octree *ocA, const D3DXMATRIX *aTrans, const Octree *ocB, const D3DXMATRIX *bTrans);

	// True if the quad is deemed small enough that it
	// shouldn't be divided anymore
	bool smallEnough;

	// True if there is something in the box
	bool isOccupied;

private:

//     L       R
//
//   -----------------
//   |\       \       \   B
//   | \-------+-------\
//   | |\       \       \   F
//   | | |-------|-------|
//   |\| |       |       |  T
//   | + |       |       |
//   | |\|       |       |
//   | | |-------+-------|
//    \| |       |       |
//     \ |       |       |  B
//      \|       |       |
//       -----------------

	union
	{
		struct
		{
			Octree *ltb;
			Octree *rtb;
			Octree *rtf;
			Octree *ltf;
			
			Octree *lbb;
			Octree *rbb;
			Octree *rbf;
			Octree *lbf;
		} tree;

		Octree *oct[8];
	};

	// BBox representing this level
	BBox box;

	// Level down
	uchar level;

	// Sets the occupied variable and creates nodes
	void Occupy();
};

#endif // __OCTREE_H__